package com.leetcode.砝码问题;

/**
 * 经典砝码问题：要想在天平上称出1到40磅在内的任何整磅数，问最少需要几个多重的砝码？
 * 这里有两种放置砝码的办法：
 * （1）所有砝码只放进天平的一端
 * （2）砝码可以放进天平的两端
 * 具体分析见：砝码问题.md
 * 这里直接给出结果
 * （1）分别设置砝码为：1，2，4，8...(2的幂)
 * （2）分别设置砝码为：1，3，9，27...(3的幂)
 * 就可以用最少的砝码数，称出1到N内的任意整数磅
 */
public class ClassicWeightsProblem {
    public static void main(String[] args) {
        int N = 40;//最大磅数
        System.out.println("最少需要几个多重的砝码，可以在天平上称出1到" + N + "磅在内的任何整磅数");
        int ans = 1;
        int cnt = 1;
        //所有砝码只放进天平的一端
        while(ans < N){
            ans += Math.pow(2,cnt);
            cnt++;
        }
        System.out.println("所有砝码只放进天平的一端需要" + cnt + "个");
        System.out.println("分别为1，2，4，8……2^" + (cnt - 1));
        ans = 1;
        cnt = 1;
        //砝码可以放进天平的两端
        while (ans < N){
            ans += Math.pow(3,cnt);
            cnt++;
        }
        System.out.println("砝码可以放进天平的两端需要" + cnt + "个");
        System.out.println("分别为1，3，9……3^" + (cnt - 1));
    }
}
